#ifndef RECURSION_H_
#define RECURSION_H_

#include <cstddef>
#include <map>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

namespace
{
// 判断所给的表达式是否有误
inline bool valid(const char* str, size_t len)
{
    std::unordered_set<char> computable;
    for (auto i :
         {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '+', '-', '*', '/', '(', ')'}) {
        computable.insert(i);
    }

    std::stack<char> bracket;
    for (size_t i = 0; i < len; i++) {
        if (computable.count(str[i]) == 0) return false;
        if (str[i] == '(') {
            bracket.push('(');
        }
        if (str[i] == ')') {
            if (bracket.empty()) return false;
            bracket.pop();
        }
    }
    return bracket.empty();
}

inline void push(std::vector<int>& numbers, std::vector<char>& ops, int cur, int op)
{
    if (numbers.empty() || ops.back() == '+' || ops.back() == '-') {
        numbers.push_back(cur);
        ops.push_back(op);
    }
    else {
        int&  top_number = numbers.back();
        char& top_op     = ops.back();
        if (top_op == '*') {
            top_number = top_number * cur;
        }
        else {
            top_number = top_number / cur;
        }
        top_op = op;
    }
}

inline int compute(const std::vector<int>& numbers, const std::vector<char>& ops)
{
    int ans = numbers[0];
    for (size_t i = 1; i < numbers.size(); i++) {
        ans += ops[i - 1] == '+' ? numbers[i] : -numbers[i];
    }
    return ans;
}

// 核心计算代码
inline int do_calculate(const char* str, size_t len, size_t& i)
{
    std::vector<int>  numbers;
    std::vector<char> ops;

    int cur = 0;
    while (i < len && str[i] != ')') {
        if ('0' <= str[i] && str[i] <= '9') {
            cur = cur * 10 + str[i++] - '0';
        }
        else if (str[i] != '(') {
            push(numbers, ops, cur, str[i++]);
            cur = 0;
        }
        else {
            i++;
            cur = do_calculate(str, len, i);
        }
    }

    push(numbers, ops, cur, '+');
    i++;
    return compute(numbers, ops);
}

inline std::string& integra(std::string& str, int count)
{
    std::string temp = str;
    while (count > 1) {
        str += temp;
        count--;
    }
    return str;
}

// 解码核心逻辑
inline std::string do_decode(const char* s, size_t len, size_t& i)
{
    std::string str("");
    int         cur = 0;
    while (i < len && s[i] != ']') {
        if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
            str += s[i++];
        }
        else if (s[i] >= '0' && s[i] <= '9') {
            cur = cur * 10 + s[i++] - '0';
        }
        else {
            i++;
            std::string temp = do_decode(s, len, i);
            str += integra(temp, cur);
            cur = 0;
        }
    }
    i++;
    return str;
}

inline void fill(std::map<std::string, int>& ans,
                 std::map<std::string, int>& pre,
                 std::string&                name,
                 int                         cnt)
{
    if (!name.empty() || !pre.empty()) {
        cnt = cnt == 0 ? 1 : cnt;
        if (!name.empty()) {
            ans[name] += cnt;
        }
        else {
            for (auto& [s, count] : pre) {
                ans[s] += count * cnt;
            }
        }
    }
}

// 解分子式核心逻辑
inline std::map<std::string, int> do_decoposeition(const std::string& s, size_t& i)
{
    // ans是总表
    std::map<std::string, int> ans;
    // 之前收集到的名字，历史的一部分
    std::string name;
    // 之前收集到的有序表，历史的一部分
    std::map<std::string, int> pre;
    // 历史翻几倍
    int cnt = 0;

    while (i < s.size() && s[i] != ')') {
        if (s[i] >= 'A' && s[i] <= 'Z' || s[i] == '(') {
            fill(ans, pre, name, cnt);
            name = "";
            pre.clear();
            cnt = 0;
            if (s[i] >= 'A' && s[i] <= 'Z') {
                name += s[i++];
            }
            else {
                i++;
                pre = do_decoposeition(s, i);
            }
        }
        else if (s[i] >= 'a' && s[i] <= 'z') {
            name += s[i++];
        }
        else {
            cnt = cnt * 10 + s[i++] - '0';
        }
    }
    fill(ans, pre, name, cnt);
    i++;
    return ans;
}
}   // namespace

namespace lxj
{
// 表达式求值 1+5*(2+(3)-(6+(9/3)),返回最小值表示表达式有误
inline int calculate(const char* str, size_t len)
{
    bool no_valid = valid(str, len);
    if (!no_valid) return 1 << 31;

    size_t where = 0;
    return do_calculate(str, len, where);
}

// 力扣394. 字符串解码
inline std::string decodeString(const std::string& s)
{
    size_t where = 0;
    return do_decode(s.c_str(), s.size(), where);
}

// 力扣726. 原子的数量
inline std::string countOfAtoms(const std::string& formula)
{
    size_t      where = 0;
    auto        map   = do_decoposeition(formula, where);
    std::string ans;
    ans.reserve(formula.size());
    for (auto& [s, cnt] : map) {
        ans += s + (cnt > 1 ? std::to_string(cnt) : "");
    }
    return ans;
}
}   // namespace lxj


#endif